package 环形链表;

import 链表相交.Demo160;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 环形链表 II,相遇点，和起始点一起出发，两者相遇点一定是是入口点
 * @date 2022/10/23 11:00
 */
public class Demo142 {
    public ListNode detectCycle(ListNode head) {
        ListNode pre=new ListNode(-1);
        pre.next=head;
        ListNode slow=pre.next;
        if(slow==null){
            return null;
        }
        ListNode fast=pre.next.next;
        while (fast!=null&&fast.next!=null&&fast!=slow){
            fast=fast.next.next;
            slow=slow.next;
        }
        if(fast==null||fast.next==null){
            return null;
        }
        //走到这里证明有环存在
        while (pre!=fast){
            pre=pre.next;
            fast=fast.next;
        }
        return fast;
    }
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
